package com.yanceysong.codetop.s1_s10;

import com.yanceysong.common.util.ArrayPrintUtil;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @ClassName S5_Mid_215_数组中的第K个最大元素
 * @Description
 * @date 2025/8/17 21:52
 * @Author yanceysong
 * @Version 1.0
 */
public class S4_Mid_215_数组中的第K个最大元素 {
    /**
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * <p>
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * <p>
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3,2,1,5,6,4], k = 2
     * 输出: 5
     * 示例 2:
     * <p>
     * 输入: [3,2,3,1,2,4,5,5,6], k = 4
     * 输出: 4
     * <p>
     * 提示：
     * <p>
     * 1 <= k <= nums.length <= 105
     * -104 <= nums[i] <= 104
     */
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k);
    }

    /**
     * ==================== 快速选择算法图解 ====================
     * <p>
     * 算法思路：基于快排的分治思想，但只处理包含目标的一侧
     * 1. 随机选择基准值(pivot)，避免最坏情况
     * 2. 将数组分为三部分：大于pivot、等于pivot、小于pivot
     * 3. 根据k的位置决定在哪一部分继续查找
     * 4. 递归处理，直到找到第k大元素
     * <p>
     * 执行示例：nums=[3,2,1,5,6,4], k=2 (找第2大元素)
     * <p>
     * 第1轮：pivot=4 (随机选择)
     * 原数组: [3, 2, 1, 5, 6, 4]
     * 分割后:
     * bigger  = [5, 6]     (大于4的元素，长度=2)
     * equal   = [4]        (等于4的元素，长度=1)
     * smaller = [3, 2, 1]  (小于4的元素，长度=3)
     * <p>
     * 判断k=2的位置：
     * - k=2 <= bigger.length=2 ✓
     * - 第2大元素在bigger数组中
     * - 递归调用：quickSelect([5, 6], 2)
     * <p>
     * 第2轮：pivot=5 (随机选择)
     * 原数组: [5, 6]
     * 分割后:
     * bigger  = [6]        (大于5的元素，长度=1)
     * equal   = [5]        (等于5的元素，长度=1)
     * smaller = []         (小于5的元素，长度=0)
     * <p>
     * 判断k=2的位置：
     * - k=2 > bigger.length=1
     * - k=2 <= bigger.length + equal.length = 1+1 = 2 ✓
     * - 第2大元素就是pivot=5
     * - 返回结果：5
     * <p>
     * 算法分析：
     * 时间复杂度：
     * - 平均情况：O(n) - 每次递归处理约一半元素
     * - 最坏情况：O(n²) - 每次都选到最值作为pivot
     * - 最好情况：O(n) - 每次都选到中位数作为pivot
     * <p>
     * 空间复杂度：O(n) - 需要创建新数组存储分割结果
     * <p>
     * 关键优化：
     * - 随机选择pivot避免最坏情况
     * - 只递归处理包含目标的一侧，减少计算量
     * - 三路分割处理重复元素
     * <p>
     * 分割策略图解：
     * <p>
     * 原数组: [a₁, a₂, ..., aₙ]
     * ↓ 选择pivot
     * <p>
     * 分割成三部分：
     * ┌─────────┬─────────┬─────────┐
     * │ bigger  │  equal  │ smaller │
     * │ > pivot │ = pivot │ < pivot │
     * └─────────┴─────────┴─────────┘
     * <p>
     * 决策逻辑：
     * if (k <= bigger.length)
     * → 在bigger中找第k大
     * else if (k > bigger.length + equal.length)
     * → 在smaller中找第(k-bigger.length-equal.length)大
     * else
     * → 答案就是pivot
     * <p>
     * ================================================================
     */
    private int quickSelect(int[] nums, int k) {
        // 步骤1：随机选择基准值，避免最坏情况O(n²)
        int randomIndex = ThreadLocalRandom.current().nextInt(nums.length);
        int pivotValue = nums[randomIndex];

        // 步骤2：三路分割 - 将数组分为三个部分
        // 使用Stream API进行函数式编程，代码简洁易懂
        int[] biggerThanPivot = Arrays.stream(nums)
                .filter(element -> element > pivotValue)
                .toArray();

        int[] equalToPivot = Arrays.stream(nums)
                .filter(element -> element == pivotValue)
                .toArray();

        int[] smallerThanPivot = Arrays.stream(nums)
                .filter(element -> element < pivotValue)
                .toArray();

        // 步骤3：根据k的位置决定在哪个区间继续查找
        // k 小于小于等于更大的一组，说明这个数字在更大的一组里面
        if (k <= biggerThanPivot.length) {
            // 情况1：第k大元素在bigger区间
            // 继续在bigger数组中找第k大元素
            return quickSelect(biggerThanPivot, k);
        } else if (k > (biggerThanPivot.length + equalToPivot.length)) {
            // 情况2：第k大元素在smaller区间
            // 需要调整k值：减去bigger和equal的长度
            int adjustedK = k - biggerThanPivot.length - equalToPivot.length;
            return quickSelect(smallerThanPivot, adjustedK);
        } else {
            // 情况3：第k大元素就是pivot值
            // k在equal区间内，所有equal元素都是第k大
            return pivotValue;
        }
    }

    public static void main(String[] args) {
        S4_Mid_215_数组中的第K个最大元素 solution = new S4_Mid_215_数组中的第K个最大元素();

        System.out.println("=== 数组中的第K个最大元素测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同K值测试
        System.out.println("\n--- 测试3: 不同K值测试 ---");
        testDifferentKValues(solution);

        // 测试4: 特殊数值测试
        System.out.println("\n--- 测试4: 特殊数值测试 ---");
        testSpecialValues(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 验证结果的辅助方法
     */
    private static int getKthLargestBySort(int[] nums, int k) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        return sorted[sorted.length - k];
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S4_Mid_215_数组中的第K个最大元素 solution) {
        // 示例1: [3,2,1,5,6,4], k=2 -> 5
        int[] nums1 = {3, 2, 1, 5, 6, 4};
        int k1 = 2;
        int expected1 = 5;

        int result1 = solution.findKthLargest(nums1.clone(), k1);

        System.out.print("输入: ");
        ArrayPrintUtil.printArray(nums1);
        System.out.println(", k=" + k1 + " -> 输出: " + result1 + " (期望: " + expected1 + ")");

        assert result1 == expected1 : "示例1测试失败";

        // 示例2: [3,2,3,1,2,4,5,5,6], k=4 -> 4
        int[] nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k2 = 4;
        int expected2 = 4;

        int result2 = solution.findKthLargest(nums2.clone(), k2);

        System.out.print("输入: ");
        ArrayPrintUtil.printArray(nums2);
        System.out.println(", k=" + k2 + " -> 输出: " + result2 + " (期望: " + expected2 + ")");

        assert result2 == expected2 : "示例2测试失败";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S4_Mid_215_数组中的第K个最大元素 solution) {
        // 测试1: 单个元素，k=1
        int[] nums1 = {1};
        int k1 = 1;
        int expected1 = 1;

        int result1 = solution.findKthLargest(nums1.clone(), k1);

        System.out.print("单个元素: ");
        ArrayPrintUtil.printArray(nums1);
        System.out.println(", k=" + k1 + " -> 输出: " + result1 + " (期望: " + expected1 + ")");

        assert result1 == expected1 : "单个元素测试失败";

        // 测试2: 两个元素，k=1（最大值）
        int[] nums2 = {1, 2};
        int k2 = 1;
        int expected2 = 2;

        int result2 = solution.findKthLargest(nums2.clone(), k2);

        System.out.print("两个元素k=1: ");
        ArrayPrintUtil.printArray(nums2);
        System.out.println(", k=" + k2 + " -> 输出: " + result2 + " (期望: " + expected2 + ")");

        assert result2 == expected2 : "两个元素k=1测试失败";

        // 测试3: 两个元素，k=2（最小值）
        int[] nums3 = {1, 2};
        int k3 = 2;
        int expected3 = 1;

        int result3 = solution.findKthLargest(nums3.clone(), k3);

        System.out.print("两个元素k=2: ");
        ArrayPrintUtil.printArray(nums3);
        System.out.println(", k=" + k3 + " -> 输出: " + result3 + " (期望: " + expected3 + ")");

        assert result3 == expected3 : "两个元素k=2测试失败";

        // 测试4: 已排序数组（升序）
        int[] nums4 = {1, 2, 3, 4, 5};
        int k4 = 3;
        int expected4 = 3;

        int result4 = solution.findKthLargest(nums4.clone(), k4);

        System.out.print("已排序升序: ");
        ArrayPrintUtil.printArray(nums4);
        System.out.println(", k=" + k4 + " -> 输出: " + result4 + " (期望: " + expected4 + ")");

        assert result4 == expected4 : "已排序升序测试失败";

        // 测试5: 已排序数组（降序）
        int[] nums5 = {5, 4, 3, 2, 1};
        int k5 = 3;
        int expected5 = 3;

        int result5 = solution.findKthLargest(nums5.clone(), k5);

        System.out.print("已排序降序: ");
        ArrayPrintUtil.printArray(nums5);
        System.out.println(", k=" + k5 + " -> 输出: " + result5 + " (期望: " + expected5 + ")");

        assert result5 == expected5 : "已排序降序测试失败";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同K值
     */
    private static void testDifferentKValues(S4_Mid_215_数组中的第K个最大元素 solution) {
        int[] nums = {7, 10, 4, 3, 20, 15};  // 排序后: [3, 4, 7, 10, 15, 20]

        // k=1: 第1大 -> 20
        testKValue(solution, nums, 1, 20, "第1大（最大值）");

        // k=2: 第2大 -> 15
        testKValue(solution, nums, 2, 15, "第2大");

        // k=3: 第3大 -> 10
        testKValue(solution, nums, 3, 10, "第3大");

        // k=4: 第4大 -> 7
        testKValue(solution, nums, 4, 7, "第4大");

        // k=5: 第5大 -> 4
        testKValue(solution, nums, 5, 4, "第5大");

        // k=6: 第6大 -> 3 (最小值)
        testKValue(solution, nums, 6, 3, "第6大（最小值）");

        System.out.println("✓ 不同K值测试通过");
    }

    /**
     * 辅助方法：测试特定K值
     */
    private static void testKValue(S4_Mid_215_数组中的第K个最大元素 solution, int[] nums, int k, int expected, String description) {
        int result = solution.findKthLargest(nums.clone(), k);

        System.out.print(description + " - ");
        ArrayPrintUtil.printArray(nums);
        System.out.println(", k=" + k + " -> 输出: " + result + " (期望: " + expected + ")");

        assert result == expected : description + "测试失败";
    }

    /**
     * 测试特殊数值
     */
    private static void testSpecialValues(S4_Mid_215_数组中的第K个最大元素 solution) {
        // 测试1: 包含负数
        int[] nums1 = {-1, 2, 0, -3, 5};  // 排序后: [-3, -1, 0, 2, 5]
        int k1 = 2;
        int expected1 = 2;  // 第2大
        testKValue(solution, nums1, k1, expected1, "包含负数");

        // 测试2: 全负数
        int[] nums2 = {-5, -2, -8, -1};  // 排序后: [-8, -5, -2, -1]
        int k2 = 1;
        int expected2 = -1;  // 第1大（最大的负数）
        testKValue(solution, nums2, k2, expected2, "全负数");

        // 测试3: 相同元素
        int[] nums3 = {1, 1, 1, 1};
        int k3 = 2;
        int expected3 = 1;
        testKValue(solution, nums3, k3, expected3, "相同元素");

        // 测试4: 大部分相同，少数不同
        int[] nums4 = {2, 2, 2, 1, 3, 2, 2};  // 排序后: [1, 2, 2, 2, 2, 2, 3]
        int k4 = 2;
        int expected4 = 2;  // 第2大
        testKValue(solution, nums4, k4, expected4, "大部分相同");

        // 测试5: 极值
        int[] nums5 = {-10000, 10000, 0};  // 排序后: [-10000, 0, 10000]
        int k5 = 1;
        int expected5 = 10000;
        testKValue(solution, nums5, k5, expected5, "极值测试");

        // 测试6: 零值
        int[] nums6 = {0, 0, 0, 1, -1};  // 排序后: [-1, 0, 0, 0, 1]
        int k6 = 2;
        int expected6 = 0;
        testKValue(solution, nums6, k6, expected6, "包含零值");

        System.out.println("✓ 特殊数值测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S4_Mid_215_数组中的第K个最大元素 solution) {
        // 测试1: 中等规模
        System.out.println("性能测试1: 1000个元素");
        testPerformanceCase(solution, 1000);

        // 测试2: 较大规模
        System.out.println("性能测试2: 10000个元素");
        testPerformanceCase(solution, 10000);

        // 测试3: 大规模
        System.out.println("性能测试3: 100000个元素");
        testPerformanceCase(solution, 100000);

        // 测试4: 最坏情况 - 所有元素相同
        System.out.println("性能测试4: 最坏情况 - 所有元素相同");
        testWorstCase(solution);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S4_Mid_215_数组中的第K个最大元素 solution, int size) {
        // 生成随机数组
        int[] nums = new int[size];
        Random random = new Random(42);  // 固定种子确保可重现
        for (int i = 0; i < size; i++) {
            nums[i] = random.nextInt(20000) - 10000;  // -10000 到 9999
        }

        int k = size / 2;  // 找中位数

        long startTime = System.currentTimeMillis();
        int result = solution.findKthLargest(nums.clone(), k);
        long endTime = System.currentTimeMillis();

        // 验证结果正确性
        int expected = getKthLargestBySort(nums, k);
        assert result == expected : "性能测试：结果不正确";

        System.out.println("  数组大小: " + size + ", k=" + k +
                           ", 结果: " + result +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度合理（应该接近O(n)）
        assert (endTime - startTime) < 5000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 辅助方法：最坏情况性能测试
     */
    private static void testWorstCase(S4_Mid_215_数组中的第K个最大元素 solution) {
        // 所有元素相同的情况
        int size = 10000;
        int[] nums = new int[size];
        Arrays.fill(nums, 42);  // 所有元素都是42

        int k = size / 2;

        long startTime = System.currentTimeMillis();
        int result = solution.findKthLargest(nums.clone(), k);
        long endTime = System.currentTimeMillis();

        // 验证结果
        assert result == 42 : "最坏情况：结果应该是42";

        System.out.println("  最坏情况测试 - 数组大小: " + size + ", k=" + k +
                           ", 结果: " + result +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        assert (endTime - startTime) < 2000 : "最坏情况：执行时间过长";
    }
}
